package pri.hillchen.algorithm.array;

/**
 * 查询两排序数组中第k小的数值
 * Created by hillchen on 2017/9/25 0025.
 */
public class FindKMin {
    class NoFindException extends RuntimeException{
        public NoFindException() {
        }

        public NoFindException(String message) {
            super(message);
        }

        public NoFindException(String message, Throwable cause) {
            super(message, cause);
        }

        public NoFindException(Throwable cause) {
            super(cause);
        }

    }
    /**
     *
     * @param arrayA
     * @param aStartIndex
     * @param aLength
     * @param arrayB
     * @param bStartIndex
     * @param bLength
     * @param k
     * @return
     */
    public int findKMin(int[] arrayA,int aStartIndex,int aLength,int[] arrayB,int bStartIndex, int bLength, int k ){
        if(aLength + bLength < k){
            throw new NoFindException("没有找到指定k大小的值，两数组可取长度之和小于k值！");
        }else if(aLength + bLength == k){
            return arrayA[aStartIndex + aLength -1] > arrayB[bStartIndex + bLength -1] ? arrayA[aStartIndex + aLength -1] : arrayB[bStartIndex + bLength -1];
        }else{

            if(aLength == 0){
                return arrayB[bStartIndex + k -1 ];
            }else if(bLength == 0 ){
                return arrayB[bStartIndex + k -1 ];
            }else{
                if(k == 1){
                    return arrayA[aStartIndex] < arrayB[bStartIndex] ? arrayA[aStartIndex] : arrayB[bStartIndex];
                }

                int kMind = k/2;
                int checkA = aStartIndex + kMind -1;
                int checkB = bStartIndex + kMind -1;
                if(kMind > aLength){
                    checkA = aStartIndex + aLength -1;
                }
                if(kMind > bLength){
                    checkB = bStartIndex + bLength -1;
                }

                if(arrayA[checkA] <= arrayB[checkB]){
                    int filterCount =   checkA + 1 - aStartIndex;
                    return findKMin(arrayA,checkA + 1, aLength - filterCount,arrayB,bStartIndex,bLength,k - filterCount);
                }else{
                    int filterCount = checkB + 1 - bStartIndex;
                    return findKMin(arrayA,aStartIndex, aLength,arrayB,checkB + 1 ,bLength - filterCount,k - filterCount);
                }

            }
        }
    }

    public static void main(String[] args){
        int[] arrayA = {1,3,4,5,6,7,8,10,15,18};
        int[] arrayB = {2,9,11,12,13,14,16,17};
        int k10 = new FindKMin().findKMin(arrayA,0,10,arrayB,0,5,12);
        System.out.println(k10 == 12 );
    }
}
